package leetcode.day;

// 28. 实现 strStr()
public class StrStr {
    public static void main(String[] args) {
        System.out.println(strStr("mississippi", "issip"));

    }
    public static int strStr(String s, String t) {
        if (t.length() == 0) {
            return 0;
        }
        int[] next = new int[t.length()];
        getNext(t, next);
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != t.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == t.charAt(j)) {
                j++;
            }
            if (j == t.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }
    private static void getNext(String s, int[] next) {
        int j = 0;
        next[0] = j; // 也就是第一个值为0
        for (int i = 1; i < s.length(); i++) {
            // 前后缀不同,返回到j指针的下一位，连续回退，所以用while
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                // 回退
                j = next[j - 1];
            }
            // 前后缀相同，移动指针
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            // next数组赋值
            next[i] = j;
        }
    }

}
